// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
// 105. 从前序与中序遍历序列构造二叉树
// 给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，
// inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点
// preorder 和 inorder 均无重复元素
import { TreeNode } from '../utils/index.ts';

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (preorder.length === 0) return null;

    const map: Map<number, number> = new Map();
    inorder.forEach((value, index) => {
        map.set(value, index);
    });

    /**
     * create binary tree from [start, end] of preorder, return root
     * @param s0 start index of preorder, inclusive
     * @param e0 end index of preorder, inclusive
     * @param s1 start index of inorder, inclusive
     * @param e1 end index of inorder, inclusive
     */
    function helper(
        s0: number,
        e0: number,
        s1: number,
        e1: number
    ): TreeNode | null {
        if (s0 > e0) return null;

        const rootVal = preorder[s0];
        const root = new TreeNode(rootVal);
        // root index of inorder
        const r = map.get(rootVal) || 0;
        const leftSize = r - s1;
        root.left = helper(s0 + 1, s0 + leftSize, s1, r - 1);
        root.right = helper(s0 + leftSize + 1, e0, r + 1, e1);
        return root;
    }

    return helper(0, preorder.length - 1, 0, inorder.length - 1);
}
